Today, networks, represented by the Internet, are widely used for providing various services. When breakdowns in switches, congestion in routers, or the like have caused failures on a transmission route for packets in such services, the receiving quality of packets deteriorates greatly. For example, an increase in a packet loss rate makes it necessary to retransmit packets, which causes problems such as taking a longer time for transmitting packets. This makes it important to rapidly respond to failures on transmission routes (networks). Accordingly, understanding the topology of a network is very important to failure analysis.
In the field of networking, design/construction departments for designing and constructing networks and management/operation departments for managing and operating such networks (responding to failures) are often separated from each other. Management/operation departments often fail to obtain the precise topology information of a network for responding to failures. Usually, it is also difficult for users of a network to obtain the topology information for analyzing the situation. In order to cope with this situation, technologies of determining (estimating) topologies of networks have been discussed in recent years.
Conventional methods of estimating topologies of networks can roughly be classified into three types: an estimation method using traceroute, an estimation method using SNMP (Simple Network Management Protocol), and an estimation method using capture of a routing protocol.
traceroute is an investigating tool (program) for investigating transfer routes from a certain observation point (investigation node) to an arbitrary destination node on a network by transmitting an investigation packet from the investigation node and receiving the response. Accordingly, in an estimation method using traceroute, this tool is used in many destination nodes, and the results obtained from the respective destination nodes are taken together so that the network topology from the investigation node is estimated. “traceroute” used herein is used as a general term for investigation tools that use investigation packets.
SNMP is a protocol for requesting and obtaining statistical information and management information (MIB: Management Information Base) accumulated in nodes on networks. In the estimation method using SNMP, SNMP is used for making requests from the investigation node and obtaining information of MIB from each node on a network, and the obtained pieces of information are taken together so as to estimate the network topology. There are various methods and protocols for obtaining information stored in nodes; however, estimation method using SNMP used herein is meant to include those various methods and protocols.
Routing protocols are for exchanging pieces of routing information. Among routing protocols, the protocols referred to as link state type permit nodes to exchange the topology information of networks and their cost information with each other. Thus, in the estimation method using capture of the routing protocol, the topology is estimated by capturing packets for exchanging at the investigation node. A representative link-state-type routing protocol is OSPF (Open Shortest Path First).
Among the above methods, according to traceroute and the estimation method using SNMP, investigation packets (or requests) have to be transmitted to the network. Such estimation methods are referred to as active search. In networks, administrators sometimes limit packet transmission for investigation on the basis of the administration policies. In such a case, network topologies cannot be estimated using active search.
Also, among the above methods, according to the estimation method using capture of the routing protocol, packets of link-state-type routing protocol have to be flowing through networks. However, there are actually not many such networks. Thus, this estimation method has a low versatility, and in many cases cannot be used for network topology estimations.
In view of this, it is desirable that an estimation of network topologies not be based on transmissions of special packets such as investigation packets or packets of routing protocols. In other words, network topologies are desirably estimated from normal packets that are flowing through networks.    Patent Document 1: Japanese Laid-open Patent Publication No. 2002-77161